package DynamicProgramming;

import java.util.Scanner;

public class 零一背包 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();//背包容量
        int n=sc.nextInt();//物品个数
        int[] w=new int[n];//重量
        int[] v=new int[n];//价值
        for (int i = 0; i < n; i++) {
            w[i]=sc.nextInt();
            v[i]=sc.nextInt();
        }
        int[][] dp=new int[n+1][m+1];//前i件物品放入容量为j的背包中获得的最大价值
        int[][] path=new int[n+1][m+1];//记录放第几个物品
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <=m ; j++) {
                if(j>=w[i-1]){//背包容量>=第i件物品体积
                    dp[i][j]=Math.max(dp[i-1][j-w[i-1]]+v[i-1],dp[i][j]);
                    if(dp[i-1][j-w[i-1]]+v[i-1]>dp[i-1][j]){
                        path[i][j]=1;
                    }
                }
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j]);//不放入，背包价值不变
            }
        }
        System.out.println(dp[n][m]);//获得最大价值

        int i= path.length-1;
        int j=path[0].length-1;
        while (i>0&&j>0){
            if(path[i][j]==1){
                System.out.println("第"+i+"个商品放入背包");
                j-=w[i-1];
            }
            i--;
        }
    }
}
